package q701_insertIntoBST;

import CommonClass.Common.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

public class Solution_1 {
    /*
    对于插入一个节点，如果是二叉搜索树
    只需要中序遍历，当找到第一个大于它的节点时，将其插入即可
    需要注意的是，如果遍历完没有找到大于它的节点，
    则需要将其插入到最后一个节点的右侧
     */
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode node = root;
        Deque<TreeNode> stack = new LinkedList<>();
        // 记录最大节点 （最后一个节点）
        TreeNode maxNode = null;
        // 中序遍历
        while (!stack.isEmpty() || node != null) {

            while (node != null) {
                stack.push(node);
                node = node.left;
            }

            node = stack.pop();
            maxNode = node;
            // 找到大于val的节点即可插入并结束
            if (val < node.val) {
                TreeNode insertNode = new TreeNode(val);
                insertNode.left = node.left;
                node.left = insertNode;
                break;
            }

            node = node.right;
        }
        // 用于处理val大于最后一个节点的情况
        if (val > maxNode.val) {
            maxNode.right = new TreeNode(val);
        }

        return root;
    }
}
